package com.zx.练习题._2020面试题;

import com.zx._12_算法.ListNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

/**
 * 扩联系
 */
@Slf4j
public class CP999_extend {

    //链表翻转，递归实现
    @Test
    public void test_reverse1() {
        reverse(ListNode.getNodes(1, 2, 3, 4)).print();
    }

    private ListNode reverse(ListNode head) {
        if (head.next == null) {
            return head;
        }

        ListNode next = head.next;
        head.next = null;

        ListNode newHead = reverse(next);
        next.next = head;

        return newHead;
    }

    //链表翻转，循序
    @Test
    public void test_reverse2() {
        ListNode head = ListNode.getNodes(1, 2, 3, 4);

        ListNode prev = null;
        ListNode cur = head;

        while (cur != null) {
            // 记录next,防止下面丢失
            ListNode next = cur.next;

            // 翻转上一个节点和当前节点
            cur.next = prev;

            // 指针向后移动一位
            prev = cur;
            cur = next;
        }
        ListNode newHead = prev;

        newHead.print();
    }

    // 倒数第K个
    @Test
    public void test_TopK() {
        ListNode head = ListNode.getNodes(1, 2, 3, 4, 5, 6, 7);
        int k = 3;

        // 第一个指针。先走K步，剩余节点数量：n - k。n是未知数，表示链表长度。
        ListNode one = head;
        for (int i = 0; i < k; i++) {
            one = one.next;
        }

        // 第二个指针从头开始走，第一个指针从正数K继续走。
        ListNode sec = head;
        while (one != null) {
            one = one.next;
            sec = sec.next;
        }

        // 第一个指针走完剩下的 n-k步。这时第二个指针也走了n-k步。第二个指针剩余节点数量为 n - (n-k)=k。就是我们需要的节点
        log.info("第K={}节点值为={}", k, sec.val);
    }


    // 环链检测
    @Test
    public void test_deadLink() {
        ListNode head = ListNode.getNodes(1, 2, 3, 4, 5, 6, 7);
        //模拟环链，7->2
        ListNode l6 = head.get(6);
        l6.next = head.get(1);

        ListNode slow = head;
        ListNode fast = head.next;

        boolean is = false;
        while (fast.next != null && fast.next.next != null) {
            if (slow.val == fast.val) {
                is = true;
                break;
            } else {
                slow = slow.next;
                fast = fast.next.next;
            }
        }

        log.info("是否为环链={}", is);
    }
}
